www.gusucode.com > VC++ 自制SQL数据库,含有服务端+客户端-源码程序 > VC++ 自制SQL数据库,含有服务端+客户端-源码程序/code/Server/BPTree.cpp
//Download by http://www.NewXing.com // BPTree.cpp : implementation file // #include "stdafx.h" #include "miniSQL.h" #include "BPTree.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////// // CBPTNode void CBPTNode::insert_key( int i, const CEntry& V ) { for( int j = keys()++; j > i; j-- ) pick_key( j ) = pick_key( j - 1 ); pick_key( i ) = V; } void CBPTNode::insert_ptr( int i, long P ) { for( int j = ptrs()++; j > i; j-- ) pick_ptr( j ) = pick_ptr( j - 1 ); pick_ptr( i ) = P; } void CBPTNode::remove_key( int i ) { for( int j = --keys(); i < j; i++ ) pick_key( i ) = pick_key( i + 1 ); } void CBPTNode::remove_ptr( int i ) { for( int j = --ptrs(); i < j; i++ ) pick_ptr( i ) = pick_ptr( i + 1 ); } int CBPTNode::find_ptr( long ptr ) { int i; for( i = ptrs() - 1; i >= 0; i-- ) if( pick_ptr( i ) == ptr ) break; return i; } int CBPTNode::lower_bound( const CEntry& V ) { int F = 0; int N = keys(); for( ; 0 < N; ) { int N2 = N / 2; int M = F + N2; if( pick_key( M ) < V ) F = ++M, N -= N2 + 1; else N = N2; } return F; } int CBPTNode::upper_bound( const CEntry& V ) { int R = lower_bound( V ); while( R < keys() && pick_key( R ) == V ) R++; return R; } void CBPTNode::init( bool Leaf ) { leaf() = Leaf; keys() = ptrs() = 0; if( Leaf ) insert_ptr( 0, -1 ); } void CBPTNode::relink( CBlock* new_block, bool dirty ) { Bptr->lock() = false; Bptr = new_block; Bptr->lock() = true; Dptr = Bptr->GetBlock(); dirty && ( Bptr->dirty() = true ); } ///////////////////////////////////////////////////////////// // CPBucket long CPBucket::insert( long PTR ) { PNode new_node; new_node.NEXT = head_posi; new_node.PTR = PTR; bktAPI->WriteRec( head_posi = bktAPI->AllocRec(), &new_node ); return head_posi; } long CPBucket::remove( long PTR ) { long last = -1; long posi = head_posi; PNode node; for( ; posi != -1; last = posi, posi = node.NEXT ) { bktAPI->ReadRec( posi, &node ); if( node.PTR == PTR ) { if( last == -1 ) head_posi = node.NEXT; else { PNode last_node; bktAPI->ReadRec( last, &last_node ); last_node.NEXT = node.NEXT; bktAPI->WriteRec( last, &last_node ); } bktAPI->RemoveRec( posi ); return head_posi; } } throw Error( ERROR_BUCKET_REMOVE, (int)PTR, CString("") ); } void CPBucket::output( RESULT& ret ) { PNode node; long posi = head_posi; while( posi != -1 ) { bktAPI->ReadRec( posi, &node ); ret.AddTail( node.PTR ); posi = node.NEXT; } } ///////////////////////////////////////////////////////////// // CBPTree CBPTree::CBPTree( const char* name, const CEntryAttr& kattr, bool dup ) : bptAPI( 0 ), bktAPI( 0 ) { bptAPI = new CFileAPI( name, ".bpt", BLOCK_SIZE, sizeof( CBPTAttr ), false ); attr.bucket = dup; attr.kattr = kattr; attr.kattr.rearrange(); attr.root = bptAPI->AllocRec(); attr.N = (BLOCK_SIZE-sizeof(int)*2-sizeof(bool)-sizeof(long)) / (attr.kattr.length+sizeof(long)); if( attr.N < 3 ) throw Error( ERROR_BPLUS_CREATE, attr.kattr.length, CString("") ); save_attr(); if( attr.bucket ) bktAPI = new CFileAPI( name, ".bkt", sizeof( PNode ), 0, false ); CBPTNode( bptAPI->FetchBlock( attr.root ), attr, true ).init( true ); } CBPTree::CBPTree( const char* name ) { bptAPI = new CFileAPI( name, ".bpt" ); load_attr(); if( attr.bucket ) bktAPI = new CFileAPI( name, ".bkt" ); else bktAPI = 0; } CBPTree::~CBPTree() { save_attr(); if( bptAPI ) delete bptAPI; if( bktAPI ) delete bktAPI; } long CBPTree::node_seek( const CEntry& KEY ) { while( !path.Empty() ) path.Pop(); long node = attr.root; while( true ) { CBPTNode N( bptAPI->FetchBlock( node ), attr, false ); if( N.leaf() ) return node; path.Push( node ); node = N.pick_ptr( N.upper_bound( KEY ) ); } } void CBPTree::node_insert( long node, const CEntry& KEY, long PTR ) { CBPTNode N( bptAPI->FetchBlock( node ), attr, true ); if( N.leaf() ) { int posi = N.lower_bound( KEY ); if( !attr.bucket ) { if( posi < N.keys() && N.pick_key( posi ) == KEY ) throw Error( ERROR_BPLUS_INSERT, 0, _T("") ); N.insert_key( posi, KEY ); N.insert_ptr( posi, PTR ); } else { if( !( posi < N.keys() && N.pick_key( posi ) == KEY ) ) { N.insert_key( posi, KEY ); N.insert_ptr( posi, -1 ); } N.pick_ptr( posi ) = CPBucket( bktAPI, N.pick_ptr(posi) ).insert( PTR ); } } else { int posi = N.lower_bound( KEY ); if( posi < N.keys() && N.pick_key( posi ) == KEY ) throw Error( ERROR_BPLUS_INSERT, 0, _T("") ); N.insert_key( posi , KEY ); N.insert_ptr( posi + 1, PTR ); } if( N.keys() >= attr.N ) { CEntry V( attr.kattr ); long new_node = bptAPI->AllocRec(); CBPTNode N1( bptAPI->FetchBlock( new_node ), attr, true ); N1.init( N.leaf() ); if( N.leaf() ) { const int half = ( attr.N + 1 ) / 2; for( int i = N.keys() - 1; i >= half; i-- ) { N1.insert_key( 0, N.pick_key( i ) ); N1.insert_ptr( 0, N.pick_ptr( i ) ); N.remove_key( i ); N.remove_ptr( i ); } V = N1.pick_key( 0 ); N1.last_ptr() = N.last_ptr(); N.last_ptr() = new_node; } else { const int half = N.keys() - ( attr.N + 1 ) / 2; for( int i = N.keys() - 1; i >= half; i-- ) { N1.insert_key( 0, N.pick_key( i ) ); N1.insert_ptr( 0, N.pick_ptr( i + 1 ) ); N.remove_key( i ); N.remove_ptr( i + 1 ); } V = N1.pick_key( 0 ); N1.remove_key( 0 ); } if( path.Size() ) { long P = path.Pop(); node_insert( P, V, new_node ); } else { long new_P = bptAPI->AllocRec(); CBPTNode P( bptAPI->FetchBlock( new_P ), attr, true ); P.init( false ); P.insert_key( 0, V ); P.insert_ptr( 0, new_node ); P.insert_ptr( 0, node ); attr.root = new_P; } } } void CBPTree::node_remove( long node, const CEntry& KEY, long PTR ) { CBPTNode N( bptAPI->FetchBlock( node ), attr, true ); if( N.leaf() ) { int posi = N.lower_bound( KEY ); if( posi < N.keys() && N.pick_key( posi ) == KEY && ( attr.bucket || N.pick_ptr( posi ) == PTR ) ) if( !attr.bucket ) { N.remove_key( posi ); N.remove_ptr( posi ); } else { N.pick_ptr( posi ) = CPBucket( bktAPI, N.pick_ptr(posi) ).remove( PTR ); if( N.pick_ptr( posi ) == -1 ) { N.remove_key( posi ); N.remove_ptr( posi ); } } else throw Error( ERROR_BPLUS_REMOVE, 0, _T("") ); } else { int posi = N.lower_bound( KEY ); N.remove_key( posi ); N.remove_ptr( posi + 1 ); } if( attr.root == node ) { if( N.ptrs() == 1 && N.pick_ptr( 0 ) != -1 ) { attr.root = N.pick_ptr( 0 ); bptAPI->RemoveRec( node ); } } else if( N.leaf() && N.keys() < attr.N / 2 || !N.leaf() && N.ptrs() < ( attr.N + 1 ) / 2 ) { bool pre; long parent_node = path.Pop(); CBPTNode P( bptAPI->FetchBlock( parent_node ), attr, true ); int posi = P.find_ptr( node ); int vposi; //KEY position if( posi == P.ptrs() - 1 ) pre = true, vposi = --posi; else pre = false, vposi = posi++; CEntry V( P.pick_key( vposi ) ); CBPTNode N1( bptAPI->FetchBlock( P.pick_ptr( posi ) ), attr, true ); if( N.keys() + N1.keys() + !N.leaf() < attr.N ) { CBPTNode *NA, *NB; if( pre ) NA = &N1, NB = &N; else NA = &N , NB = &N1; if( !N.leaf() ) { NA->insert_key( NA->keys(), V ); int i; for( i = 0; i < NB->keys(); i++ ) { NA->insert_key( NA->keys(), NB->pick_key( i ) ); NA->insert_ptr( NA->ptrs(), NB->pick_ptr( i ) ); } NA->insert_ptr( NA->ptrs(), NB->pick_ptr( i ) ); } else { for( int i = 0; i < NB->keys(); ++i ) { NA->insert_key( NA->keys(), NB->pick_key( i ) ); NA->insert_ptr( NA->ptrs() - 1, NB->pick_ptr( i ) ); } NA->last_ptr() = NB->last_ptr(); } node_remove( parent_node, V, 0 ); } else if( pre ) if( !N.leaf() ) { N.insert_key( 0, V ); N.insert_ptr( 0, N1.last_ptr() ); V = N1.last_key(); N1.keys()--; N1.ptrs()--; } else { N.insert_key( 0, N1.last_key() ); N.insert_ptr( 0, N1.pick_ptr( N1.ptrs() - 2 ) ); V = N.pick_key( 0 ); N1.keys()--; N1.remove_ptr( N1.ptrs() - 2 ); } else if( !N.leaf() ) { N.insert_key( N.keys(), V ); N.insert_ptr( N.ptrs(), N1.pick_ptr( 0 ) ); V = N1.pick_key( 0 ); N1.remove_key( 0 ); N1.remove_ptr( 0 ); } else { N.insert_key( N.keys(), N1.pick_key( 0 ) ); N.insert_ptr( N.ptrs() - 1, N1.pick_ptr( 0 ) ); N1.remove_key( 0 ); N1.remove_ptr( 0 ); V = N1.pick_key( 0 ); } } } bool CBPTree::convert( CEntry& ret, const CEntry& E, bool strict ) { if( strict && ret.values() != E.values() ) return false; try { for( int i = ret.values() - 1; i >= 0; i-- ) ret[i] = E[ attr.kattr.attr[i].name ]; } catch( Error& e ) { if( strict && e.m_ErrType == ENTRY_RANGE_ERROR ) return false; throw e; } return true; } bool CBPTree::search( RESULT& ret, const CEntry& E ) { CEntry KEY( attr.kattr ); if( !convert( KEY, E, true ) ) return false; CBPTNode N( bptAPI->FetchBlock( node_seek(KEY) ), attr, false ); int posi = N.lower_bound( KEY ); if( posi < N.keys() && N.pick_key( posi ) == KEY ) { if( !attr.bucket ) ret.AddTail( N.pick_ptr( posi ) ); else CPBucket( bktAPI, N.pick_ptr(posi) ).output( ret ); } return true; } bool CBPTree::search( RESULT& ret, const CEntry& E1, const CEntry& E2 ) { CEntry KEY1( attr.kattr ), KEY2( attr.kattr ); if( !convert( KEY1, E1, true ) || !convert( KEY2, E2, true ) ) return false; long node, last_node; int posi, last_posi; CBPTNode N( bptAPI->FetchBlock( last_node=node_seek(KEY2) ), attr, false ); last_posi = N.upper_bound(KEY2); N.relink( bptAPI->FetchBlock( node=node_seek(KEY1) ), false ); posi = N.lower_bound(KEY1); while( node != last_node || posi < last_posi ) { if( posi == N.keys() ) { if( ( node = N.last_ptr() ) == -1 ) break; N.relink( bptAPI->FetchBlock(node), false ); posi = -1; } else if( !attr.bucket ) ret.AddTail( N.pick_ptr( posi ) ); else CPBucket( bktAPI, N.pick_ptr(posi) ).output( ret ); ++posi; } return true; }